In wireless mesh networks of communication devices, messages are sent in small parts called packets. Packets contain information about their recipient and are transmitted in general mesh networks from the sender to a sequence of devices until they reach the recipient. Defining the path, i.e. deciding which devices the packets will be transmitted through, is called routing. The goal of routing is to ensure the most reliable and fastest possible delivery of the packet from the sender to the recipient.
Mesh networks represent the most general network topology, where in general connections may exist between any two devices in the network, which means that these devices may mutually communicate and transfer messages. A mesh network where a connection can be established between any two devices in the network is called a fully connected mesh network; however, in practice the much more frequent case is that only some devices may establish mutual connections. The simplest example for a mesh network and routing is imagining the network as cities which are interconnected by the road network and routing as the journey of a vehicle with its cargo (the packet) from the city of the sender to the recipient. The vehicle travels from one city to another utilizing the existing road network. Individual roads connecting cities represent the connections between them. The whole journey from the starting point to the endpoint is thus divided into individual roads, which we call connections in the context of general networks. In the listed example there exist many different routes which the vehicle can use to transport the cargo from the city of the sender to the city of the recipient, and similarly in wireless real-world mesh networks there can exist many different routes for routing the packet from the sender to its recipient.
Since general mesh networks may or may not contain a connection between any pair of devices, the number of total possible connections in a network with n devices will always be lower or equal to Nmax where Nmax=n*(n−1)/2. In the concrete example with cities, this is the maximum number of roads in the road network between n cities.
In wireless mesh networks, devices communicate wirelessly, generally via radio waves. Connections between two communicating devices are thus usually limited by the range of these devices. Devices which are too far from each other cannot establish a mutual connection. Since the distances between individual devices are not usually known in advance in general wireless mesh networks, it is not clear in advance which devices may establish mutual connections, and thus routing, i.e. finding the route between the sender device to the recipient device of the packet, is a relatively difficult algorithmic problem, especially due to the number of possible routes and combinations of various connections.
Various routing methods for communication in mesh networks are used in practice. These include for instance routing based on routing tables, often used in computer technology, flooding or random routing. Routing based on sharing and distribution of routing tables or vectors is one of the most optimal methods with respect to the efficiency of packet delivery, however this comes at the cost of high requirements on the memory of the control processor or microcontroller of communication devices, especially in large networks with many devices. Flooding an unordered network, based on distributing a packet gradually into the whole network is a solution suitable for the reliable delivery of the packet, however is far from optimal due to the specific properties of wireless networks, which generally have low data transfer speeds and problems with media sharing (conflicts in media access and their solution). In the example above, this approach would mean traversing the whole road network in our vehicle. Random routing is used in computer technology e.g. when the router is overloaded and may reduce packet loss, but is not suitable for wireless mesh networks for telemetry due to its low reliability.
Contrary to connected systems, where individual devices may have dedicated connections between them, wireless mesh networks share the communication spectrum. Inappropriate use of the communication spectrum and non-adherence to communication rules would lead to collisions of individual communication connections, preventing efficient communication. In our example with the road network, this would be analogous to the chaos and collisions leading to the closure of many roads which would occur if vehicles didn't follow rules such as which side of the road to use and which vehicle takes precedence.
Various techniques to prevent collision states are thus used for communication in wireless networks. The most frequently used methods are to define rules on WHEN each device may transmit (so-called Time Division Multiplexing or Time Division Multiple Access—TDMA) and also WHERE each device may transmit, i.e. which frequencies (usually specified by a channel) may be used by each communication device. Other techniques for media/spectrum access are also used in practice. CSMA, CDMA, TDMA or TMPS are only a few examples.
TDMA is often used in practice to prevent transmission collisions due to its easy implementation and reliability. TDMA is based on the fact that in a given time interval, called a time slot, only a single specified device may transmit. A group of time slots belonging to different participants is called a frame. On our road network example, the easiest way of illustrating this approach is using traffic lights, which limit traffic on shared crossroads in time-defined intervals.
Since most RF circuits today allow receiving and sending on several frequencies, many systems also utilize frequency hopping (FHSS—Frequency Hopping Spread Spectrum), where either individual bits or, more commonly, groups of bits are transmitted on different frequencies. In practice this means that they may be transmitted simultaneously, since they do not interfere with each other. This manner of communication may be illustrated in our example as having multi-lane roads between cities, where several vehicles may drive on a single road simultaneously.
As mentioned above, a general mesh network with n communication devices allows at most Nmax connections between communication devices, where Nmax=n*(n−1)/2, with n being the number of communication devices in the network. Since the topology of a general wireless mesh network is not known in advance, the limit case of applying collision-free flooding via TDMA would require dedicating up to Nmax time slots for individual routings to ensure reliable delivery of the packet. However, this would be very time-inefficient. For instance, for the commonly used speed of 19.2 kbit/s, the transmission of a single short packet with 24 B of data in a network with 100 communication devices would result in a frame of up to 50 seconds.
Wireless mesh networks are becoming increasingly popular for telemetry and automation as well as for many other applications. The areas of long-range reading of measuring devices, control of public lighting or distribution monitoring are good examples. In these cases the networks comprise hundreds or thousands of devices, which leads to an immense pressure on the price of communication devices and also on ensuring reliable and fast message delivery. Creation of a functional layout of the wireless network using packet transmission and comprising tens, hundreds or thousands of devices is an immensely difficult algorithmic process due to the gigantic amount of various layouts of such a network. This is further complicated for networks comprising communication devices with limited hardware resources (program and data memory) and communicating at low speeds, especially in the case of multiple-routing, i.e. the transfer of messages from one device to another.
Various techniques for obtaining the layout of wireless mesh networks and routing algorithms are the subject of scientific research. For instance, a conference was held in 2010 in Venice (http://www.iaria.org/conferences2010/MESH10.html).
Commercially available implementations of protocols supporting wireless mesh networks also exist. One example is Zigbee (http://www.zigbee.org), which implements the IEEE 802.15.4 standard. Another example is the SmartMesh technology of Dust Networks (http://www.dustnetworks.com). The demands on processor resources, and especially high requirements on the program and data memory of the microcontroller, has led to many attempts to limit the number of supported devices and routings in the network, which would significantly simplify implementation. One example of such a technology is MiWi (http://www.microchip.com/miwi), which is again based on the IEEE 802.15.4 standard but limits the number of routings to 4. The main reason for the high memory requirements is the fact that most technologies use routing tables for routing. Their size grows proportionally to the number of supported devices and the number of possible routings in the wireless mesh network.
The small number of possible routings, limited number of communication devices in a single network, low efficiency of collision algorithms, and the high requirements on used hardware prevent the application of many solutions in large networks requiring hundreds or thousands of communication devices connected in a general wireless mesh networks.